class Solution
{
public:
    int count(string num1, string num2, int min_sum, int max_sum)
    {
        int result = countFromOne(num2, min_sum, max_sum);

        for (int i = num1.size() - 1; i >= 0; --i)
        {
            if (num1[i] == '0')
            {
                num1[i] = '9';
            }
            else
            {
                num1[i] -= 1;
                break;
            }
        }

        if (num1 == "0")
        {
            return result;
        }
        if (num1[0] == '0')
        {
            num1.erase(num1.begin());
        }

        result -= countFromOne(num1, min_sum, max_sum);
        return (result + 1'0000'0000'7) % 1'0000'0000'7;
    }

    int countFromOne(string &upper, int minSum, int maxSum)
    {
        int len = upper.size();
        vector<vector<vector<int>>> dp(len, vector<vector<int>>(2, vector<int>(maxSum + 1, 0)));

        for (int digit = 0; digit <= min(maxSum, 9); ++digit)
        {
            if (digit == upper[0] - '0')
            {
                dp[0][1][digit] = 1;
                break;
            }
            else
            {
                dp[0][0][digit] = 1;
            }
        }

        for (int i = 1; i < len; ++i)
        {
            for (int digit = 0; digit <= 9; ++digit)
            {
                for (int targetSum = 0; targetSum <= maxSum; ++targetSum)
                {
                    if (targetSum - digit >= 0)
                    {
                        if (digit < upper[i] - '0')
                        {
                            dp[i][0][targetSum] += dp[i - 1][0][targetSum - digit];
                            dp[i][0][targetSum] += dp[i - 1][1][targetSum - digit];
                            dp[i][0][targetSum] %= 1'0000'0000'7;
                        }
                        else if (digit == upper[i] - '0')
                        {
                            dp[i][0][targetSum] += dp[i - 1][0][targetSum - digit];
                            dp[i][1][targetSum] += dp[i - 1][1][targetSum - digit];
                            dp[i][0][targetSum] %= 1'0000'0000'7;
                            dp[i][1][targetSum] %= 1'0000'0000'7;
                        }
                        else
                        {
                            dp[i][0][targetSum] += dp[i - 1][0][targetSum - digit];
                            dp[i][0][targetSum] %= 1'0000'0000'7;
                        }
                    }
                }
            }
        }

        int result = 0;
        for (int sum = minSum; sum <= maxSum; ++sum)
        {
            result += (dp[len - 1][0][sum] + dp[len - 1][1][sum]);
            result %= 1'0000'0000'7;
        }

        return result;
    }

    // 单独统计每个sum会超时
    int countFromOneRange(string &upper, int min_sum, int max_sum)
    {
        int result = 0;
        for (int targetSum = min_sum; targetSum <= max_sum; ++targetSum)
        {
            result += countFromOneWithSum(upper, targetSum);
            result %= 1'0000'0000'7;
        }
        return result;
    }

    // O(10 * L * sum)
    int countFromOneWithSum(string &upper, int sum)
    {
        int len = upper.size();
        vector<vector<vector<int>>> dp(len, vector<vector<int>>(2, vector<int>(sum + 1, 0)));

        for (int digit = 0; digit <= min(sum, 9); ++digit)
        {
            if (digit == upper[0] - '0')
            {
                dp[0][1][digit] = 1;
                break;
            }
            else
            {
                dp[0][0][digit] = 1;
            }
        }

        for (int i = 1; i < len; ++i)
        {
            for (int digit = 0; digit <= 9; ++digit)
            {
                for (int targetSum = 0; targetSum <= sum; ++targetSum)
                {
                    if (targetSum - digit >= 0)
                    {
                        if (digit < upper[i] - '0')
                        {
                            dp[i][0][targetSum] += dp[i - 1][0][targetSum - digit];
                            dp[i][0][targetSum] += dp[i - 1][1][targetSum - digit];
                            dp[i][0][targetSum] %= 1'0000'0000'7;
                        }
                        else if (digit == upper[i] - '0')
                        {
                            dp[i][0][targetSum] += dp[i - 1][0][targetSum - digit];
                            dp[i][1][targetSum] += dp[i - 1][1][targetSum - digit];
                            dp[i][0][targetSum] %= 1'0000'0000'7;
                            dp[i][1][targetSum] %= 1'0000'0000'7;
                        }
                        else
                        {
                            dp[i][0][targetSum] += dp[i - 1][0][targetSum - digit];
                            dp[i][0][targetSum] %= 1'0000'0000'7;
                        }
                    }
                }
            }
        }

        int result = (dp[len - 1][0][sum] + dp[len - 1][1][sum]) % 1'0000'0000'7;
        return result;
    }
};